/*
链表
每一个元素是一个节点/结点，包括数据域和指针域

链表分为单链表和双链表
单链表：
	每个节点只有一个指针域，指向下一个节点
    尾节点的指针域指向NULL
    链表头节点的指针域指向第一个节点
双链表：
	每个节点有两个指针域，分别指向前一个节点和后一个节点
    尾节点的指针域指向NULL
    链表头节点的指针域指向第一个节点

 */
 
#include <stdio.h>
#include <stdlib.h>
#include <string.h>

typedef int ElemType;

typedef struct Node
{
    int data;
    struct Node *next;
} Node;

//初始化单链表
Node* InitList()
{
    Node* head = (Node*)malloc(sizeof(Node));
    head->data = 0;
    head->next = NULL;
    return head;
}

//头插入结点(在头结点后面插入)，先把新节点的指针域指向第一个节点，再把头指针的指针域指向新节点
void InsertHead(Node* L,ElemType e)
{
    Node* p = (Node*)malloc(sizeof(Node));
    p->data = e;
    p->next = L->next;//L->next原来是NULL,赋值给p->next
    L->next = p;//p覆盖原来的L->next
}
/*L 是传递进来的链表的头指针（即头结点），
而 L->next 指向的是头结点之后的第一个实际数据节点。*/

//尾插入结点，先要找到尾结点
Node* GetTail(Node* L)
{
    Node* p = L;
    while(p->next != NULL)
    {
        p = p->next;
    }
    return p;
}
Node* InsertTail(Node* Tail,ElemType e)
{
    Node* p = (Node*)malloc(sizeof(Node));
    p->data = e;
    Tail->next = p;
    p->next = NULL;
    return p;
}

//在指定位置插入
void InsertNode(Node* L, int pos, ElemType e)
{
    Node* p = L;
    int i = 0;
    while(i<pos-1)
    {
        p = p->next;//找到插入位置的前一个结点
        i++;
        if(p == NULL)
        {
            printf("插入位置不合法\n");
            return;
        }
    }

    //要插入的新节点
    Node* q = (Node*)malloc(sizeof(Node));
    q->data = e;
    q->next = p->next;
    p->next = q;
    printf("插入成功\n");
}

//删除指定位置的结点
void DeleteNode(Node* L, int pos)
{
    //找到指定位置的前一个结点
    Node* p = L;
    int i = 0;
    while(i < pos - 1)
    {
        p = p->next;
        i++;
    }
    if(p->next == NULL)
    {
        printf("删除位置不合法\n");
        return;
    }

    //q指向要删除的节点
    Node* q = p->next;
    p->next = q->next;
    //释放要删除节点的内存
    free(q);
}

//获取链表长度
int GetLength(Node* L)
{
    int len = 0;
    Node* p = L;
    while(p->next != NULL)
    {
        len++;
        p = p->next;
    }
    return len;
}

//释放链表
void FreeList(Node* L)
{
    Node* p = L->next;//p指向第一个节点，头结点暂时不释放
    Node* q = NULL;
    while(p != NULL)
    {
        q = p->next;
        free(p);
        p = q;
    }
    L->next = NULL;//不释放头结点
    //free(L);//释放头结点
}

//遍历单链表
void TraverseList(Node* L)
{
    Node* p = L->next;
    while(p!=NULL)
    {
        printf("%d ",p->data);
        p = p->next;
    }
    printf("\n");
}

int main()
{
    //初始化单链表
    Node* list = InitList();

    //头插入结点
    printf("头插入节点------------------\n");
    InsertHead(list, 1);
    InsertHead(list, 2);
    InsertHead(list, 3);
    printf("当前链表为：\n");
    TraverseList(list);

    //尾插入结点
    printf("尾插入节点------------------\n");
    Node* tail = GetTail(list);
    tail = InsertTail(tail, 4);
    tail = InsertTail(tail, 5);//插入后更新尾结点，不用每次都GetTail()
    tail = InsertTail(tail, 6);
    printf("当前链表为：\n");
    TraverseList(list);

    //指定位置插入节点
    printf("指定位置插入节点------------------\n");
    InsertNode(list,7,7);
    printf("当前链表为：\n");
    TraverseList(list);

    //删除指定位置节点
    printf("删除指定位置节点------------------\n");
    DeleteNode(list,7);
    printf("当前链表为：\n");
    TraverseList(list);

    //获取链表长度
    printf("链表长度为：%d\n",GetLength(list));

    //释放链表
    printf("释放链表------------------\n");
    FreeList(list);
    printf("当前链表为：\n");
    TraverseList(list);

    return 0;
}